Ville Kyrki June 20, 2002
Lappeenranta University of Tecnology
Department of Information Technology

IPCV 2002, Koblenz, Germany

Practice session: Hough transform

The task of this practice session is to implement the Hough transform using Matlab and answer a few questions about the Hough transform. The task should be completed in pairs. The program must be demonstrated to the teaching assistant at the exercise session on Tuesday (July 23). At the same time, a sheet with answers to the questions at the end of this document should be returned to the teaching assistant. Remember also to include the names of all participating students.

First, let us define the Hough transform algorithm for finding a single line in an image:

1. Create a list of edge points in a binary image.
2. Transform each edge point into a parameterised curve and accumulate.
3. Detect the maximum in the accumulator array. The maximum corresponds to the most prominent line in the image.

Simplifications and details

Only one line must be found in the image. The line should correspond to the maximum of the accumulator. The input image is square, that is, it has an equal number of rows and columns. The size of the accumulator should be the same as the image.

Hints for implementing the algorithm

Do not try to build the complete functionality at once. Build small parts which you can test with simple data.

Step 1:
You can use the matlab function find. Try help find in Matlab. Notice that in Matlab the first index refers to the row (y-coordinate) of a matrix, and the second one corresponds to the column number (x-coordinate).

Step 2:
Use the normal-form parameterisation of the line,

$$\rho=x\cos\theta + y\sin\theta,$$ (1)

where $\rho$ is the perpendicular distance from the line to origin, and $\theta$ is the angle between the normal of the line and x-axis. See the figure below.

Figure 1: Each point of the image (on left) is projected into a sinusoidal curve in accumulator (on right) using equation (1). The intersection of curves represents the line connecting the points.

Now, $\theta$ can have values between $0$ and $\pi$. If the lengths of both axes of an image are $n$, $\rho$ can have values between $-n$ and $\sqrt{2}n$. You must first find out, how to tranform the values of $\rho$ and $\theta$ to corresponding accumulator indices. Do this by deriving the linear scaling from $[1\ldots k]$ to $[a \ldots b]$. Now, substitute $a$ and $b$ with the minimum and maximum values for $\rho$ and $\theta$ and you will have the scaling equation.

Remember that the accumulation is only the incrementation of a cell in accumulator by one. That is, if $A$ is the accumulator, and the cell with indices $i_\theta$ and $i_\rho$ is accumulated, we can write $A(i_\theta,i_\rho)=A(i_\theta,i_\rho)+1$.

Step 3:
You can find the maximum in a matrix using function max. You may also need find or ind2sub depending on your implementation.

Additional tips

Function I = drawline(RHO,THETA,IM) is provided for making test images. Try help drawline.

You can try to view the accumulator after the accumulation loop. imagesc(accumulator); should give something like the following image. Try this with colormap(jet);.

Questions

Question 1: How many points on a line you need to detect a line using the Hough transform?

Question 2: How would you detect multiple lines in a single image using the Hough transform? How would multiple lines appear in the accumulator?

Question 3: How would isolated noise points appear in the accumulator, and what is their effect on the detection?

function [rho,theta] = hough(I)
% [rho,theta] = hough(I) 
%    finds a line in the input image I.

% Find out the size of the image 
isize=size(I,1);

% Check that the input image is square
if isize~=size(I,2),
  error('The input image must be square.');
end;

% Calculate the minimum and maximum values for rho
rhomin=-isize;
rhomax=sqrt(2)*isize;

% Create the list of edge points

% ... insert your code here

% Initialize accumulator
accumulator = zeros(isize);

% For each edge point,
%     For each possible value of theta,
%         Calculate the value for rho
%         Calculate the corresponding index of accumulator
%             (by scaling the values of rho and theta to 1..isize)
%         Accumulate the accumulator cell

% ... insert your code here

% Find the maximum of accumulator
% Calculate the corresponding values of rho and theta

% ... insert your code here